package com.lcm.algorithm.datatest.array;

/**
 * @description:11. 盛最多水的容器
 * 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。
 * 在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，
 * 使得它们与 x 轴共同构成的容器可以容纳最多的水。
 *
 * 说明：你不能倾斜容器，且 n 的值至少为 2。
 * 图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
 * 示例：
 * 输入：[1,8,6,2,5,4,8,3,7]
 * 输出：49
 * @author: lcm
 * @create: 2020-04-03 11:31
 **/

public class MaxArea {

    public static void main(String[] args){
        //int[] nums=new int[]{1,8,6,2,5,4,8,3,7};
        //int[] nums=new int[]{2,3,10,5,7,8,9};
        int[] nums=new int[]{2,3,4,5,18,17,6};
        System.out.println(maxArea1(nums));
        System.out.println(maxArea2(nums));
        System.out.println(maxArea3(nums));
    }

    /**
     * 1暴力解法：计算所有子数组容器值，获取最大值，O(n^2)
     * 	453 ms	40.6 MB
     * @param height
     * @return
     */
    public static int maxArea1(int[] height){
        int max=0;
        for(int i=0;i<height.length;i++){
            for(int j=i+1;j<height.length;j++){
                max=Math.max(max,Math.min(height[i],height[j])*(j-i));
            }
        }
        return max;
    }

    /**
     * 2.优化暴力：
     * 413 ms	39.9 MB
     * @param height
     * @return
     */
    public static int maxArea2(int[] height){
        int max=0;
        for(int i=0;i<height.length;i++){
            int maxi=height.length-1;
            max=Math.max(max,Math.min(height[i],height[maxi])*(maxi-i));
            for(int j=height.length-1;j>i;j--){
                if(height[j]>height[maxi]){
                    max=Math.max(max,Math.min(height[i],height[j])*(j-i));
                    maxi=j;
                }
            }
        }
        return max;
    }

    /**
     * 3.双指针法：
     * 	4 ms	39.7 MB
     * 这种方法背后的思路在于：
     * 1两线段之间形成的区域总是会受到其中较短那条长度的限制。
     * 2此外，两线段距离越远，得到的面积就越大。
     * @param height
     * @return
     */
    public static int maxArea3(int[] height){
        int left=0;
        int right=height.length-1;
        int max=0;
        while(left<right){
            max=Math.max(max,Math.min(height[left],height[right])*(right-left));
            if(height[left]>height[right]){
                right--;
            }else{
                left++;
            }
        }
        return max;
    }


}
